1. Field of the Invention
The invention relates in general to method and apparatus for recognizing patterns and in particular to method and apparatus for recognizing multifont machine printed characters.
There are many character recognition schemes relative to multifont machine printed characters. Such techiques can be used for automatically reading characters from documents such as the check number or check courtesy amounts, or any document containing strings of characters. The manual encoding of the check amount in magnetic ink for automatic document processing (MICR) represents a significant cost to the banking industry. A courtesy amount reader should be able to reduce this cost either through automatic MICR encoding or direct input to data processing systems. Basically, a courtesy amount reader must be capable of optically scanning a specified area of a document extracting the courtesy amount and recognizing each character of the courtesy amount. If the courtesy amount reader is to be able to handle successfully a significant percentage of documents, the character recognition algorithm must have multifont capabilities. The set of characters which must be recognized includes those normally encountered in courtesy amounts. This set includes the numerals 0 through 9 and five special characters, the dollar sign, the dash, the comma, the period and the asterisk.
The manual processing of any type of large volume bills, such as electrical or telephone company bills, constitutes an expensive and slow process. In this application, where the company has control of the printing process, the number of fonts is limited and the location of the characters within a relatively narrow band (or window so called) across the document can be controlled. The set of characters will generally be the digits 0 through 9, as well as special symbols used as field markers. Thus, an optical character recognition system that reads and recognizes a single row of characters located in a narrow band across a document is also highly desireable.
2. Prior Art
One of the first classification techniques tried is attributed to C. K. Chow whose technique is shown in U.S. Pat. No. 3,341,841 and also appears in IRE Transactions on Electronic Computers, Volume EC-6, page 247, December 1957. Chow's technique involves selecting prototype characters from a number of different classes of characters and thereafter forming feature vectors for the prototypes. An average vector of the prototypes from each of the classes is then formed. The dot product between an unknown character and each average vector is then formed in order to determine the cosine of the angle between the unknown vector and each average vector. If a particular dot product is large, the angle is small and the unknown is similar to the particular class of characters represented by that average vector. The dot product can also be viewed as a projection of the unknown vector onto each average vector. The unknown vector can thereafter be classified by selecting the largest projection.
Two comments can be made regarding this technique. First, by definition the technique searches for average features. In the multifont case, the average features may not be sufficient for classification purposes. Consequently, this technique would be better suited to a single font. The second comment concerns the type of decision process available using this technique. Classification only on the basis of the maximum projection involves a large risk. Requiring the maximum projection to be greater than all others by some amount reduces the risk but may reduce a larger number of rejects depending upon the exact problem.
Another method for recognizing characters is called the subspace method. The subspace method is based on the assumption that there exist class dependent coordinate systems such that the important (or weights) of the coordinate axis are not uniform. See George Nagey proceedings of the IEEE 56,836, (1968) and Watanabe et al "Evaluation of the Selection of Variables in Pattern Recognition" in Computer and Information Sciences, II edited by J. T. Tou. The Nagey reference deals with a covariance matrix which has a shortcoming in that the average features of a character are lost by subtracting the average vector from the feature vector. The Watanabe et al reference discloses a projection method for expanding a feature vector having unit length on a subspace.
An apparatus constructed in accordance with the instant invention for recognizing a presented pattern as being one of a plurality of predetermined classes of patterns comprises generating means, projecting means and selector means. The generating means generates predetermined combination of signals representing the geometric configuration of the presented pattern. The predetermined combination of signals defines a feature vector of the presented pattern. The projecting means projects the feature vector onto a set of predetermined multi-dimensional subspaces which characterize the predetermined classes. The selector means selects one of the patterns as a presented pattern according to a predetermined algorithm employing the results of the projections prior to the time that the entire projecting process is completed.
A method as defined by the instant invention for recognizing a presented pattern as being in one of a plurality of predetermined classes of patterns comprises the following steps. One, generating a predetermined combination of signals representing the geometric configuration of the presented pattern. The presented combination of signals defines a feature vector of the presented pattern. Two, the feature vector is projected onto a set of predetermined multi-dimensional subspaces characterizing the predetermined classes. And three, one of the patterns is selected as the presented pattern according to a predetermined algorithm employing the results of the projections prior to the entire projection process being completed.
The present disclosed embodiment is designed to recognize a single horizontal row of characters on a document wherein the row is located within a one half inch band and wherein characters cannot be located vertically above each other or touch each other.